package 七哈希表;

/**
 * @Author XuZhuHong
 * @CreateTime 2021/9/24 9:08
 * 9.1 哈希表(散列)-Google 上机题
 * 1) 看一个实际需求，google 公司的一个上机题:
 * 2) 有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,住址..),当输入该员工的 id 时,要求查
 * 找到该员工的 所有信息. 3) 要求: 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列
 */
public class HashTabDemo {
    public static void main(String[] args) {
        //控制有多少个数组长度
        int k = 20;
        HashTab hashTab = new HashTab(k);
        for (int i = 0; i < k * 10; i++) {
            int random = (int) (Math.random() * i * k);
            Emp emp = new Emp(random, "NAME" + random);
            //添加随机的元素进去
            hashTab.add(emp);
        }
        System.out.println("----------------------------遍历所有链表---------------------------");
        hashTab.list();
        System.out.println("----------------------------遍历完成---------------------------");

        int random = (int) (Math.random() * 10 * k);
        //差找员工
        hashTab.findEmpById(random);
        random = (int) (Math.random() * 10 * k);
        //删除员工
        hashTab.deleteEmpById(random);
        System.out.println("----------------------------遍历所有链表---------------------------");
        hashTab.list();
        System.out.println("----------------------------遍历完成---------------------------");

    }

}

//创建 HashTab 管理多条链表
class HashTab {
    private EmpLinkedList[] empLinkedListArray;
    private int size; //表示有多少条链表

    public HashTab(int size) {
        this.size = size;//记录这个数组多长
        empLinkedListArray = new EmpLinkedList[size];
        for (int i = 0; i < size; i++) {
            //在每次赋值的时候初始化一个对象给他，不然后面会报空异常
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    //删除员工
    public void deleteEmpById(int id) {
        int i = hashFun(id);
        boolean b = empLinkedListArray[i].deleteEmpById(id);
        if (b) {
            System.out.println("删除成功");
        } else {
            System.out.println("删除失败");
        }
    }

    //查找员工
    public void findEmpById(int id) {
        int i = hashFun(id);
        Emp empById = empLinkedListArray[i].findEmpById(id);
        if (empById != null) {
            System.out.println("找到了信息为" + empById);
        } else {
            System.out.println("没找到");
        }
    }

    //遍历员工
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].list();
        }
    }

    //添加员工
    public void add(Emp emp) {
        int i = hashFun(emp.getId());
        //先知道在哪个数组中添加 然后再进行添加
        empLinkedListArray[i].add(emp);
    }

    //返回应该在哪里添加的方法
    public int hashFun(int id) {
        return id % size;
    }

}

//创建 EmpLinkedList ,表示链表
class EmpLinkedList {
    private Emp head;

    //遍历
    public void list() {
        if (head == null) {
            System.out.println("没有员工");
        } else {
            Emp temp = head;
            for (; temp != null; temp = temp.next) {
                System.out.print(temp + "\t");
            }
            System.out.println();
        }
    }

    //添加一个员工
    public void add(Emp emp) {
        if (head == null) {
            head = emp;
        } else {
            Emp temp = head;
            for (; temp.next != null; temp = temp.next) ;
            temp.next = emp;
        }
    }

    //删除员工
    public boolean deleteEmpById(int id) {
        if (head == null) {
            return false;
        } else {
            Emp temp = head;
            while (true) {
                if (temp.next == null) {
                    break;
                }
                if (temp.next.getId() == id) {
                    System.out.println("删除的信息为：" + temp.next);
                    temp.next = temp.next.next;
                    return true;
                }
                temp = temp.next;
            }

            return false;
        }
    }

    //差找员工
    public Emp findEmpById(int id) {
        if (head == null) {
            return null;
        } else {
            Emp temp = head;
            for (; temp.next != null; temp = temp.next) {
                if (temp.getId() == id) {
                    return temp;
                }
            }
            return null;
        }
    }
}


//创建一个节点类
class Emp {
    private int id;
    private String name;
    public Emp next;

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Emp getNext() {
        return next;
    }

    public void setNext(Emp next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}
